package com.cty.fourteenthDay;

import java.util.Arrays;

/*
 *
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题
 * */
public class Q_16 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] res = productExceptSelf2(nums);
        System.out.println(Arrays.toString(res));
    }

    // 主包自己写的解法 左右前缀积 时间复杂度O(n) 空间复杂度O(n) 记录当前元素的左积 和 右积 直接相乘即可
    public static int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        int[] res = new int[n];
        // 左边元素的乘积和 和 右边元素的乘积和
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                left[i] = nums[i];
            } else {
                left[i] = left[i - 1] * nums[i];
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1) {
                right[i] = nums[i];
            } else {
                right[i] = right[i + 1] * nums[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res[i] = right[i + 1];
            } else if (i == n - 1) {
                res[i] = left[i - 1];
            } else {
                res[i] = right[i + 1] * left[i - 1];
            }
        }
        return res;
    }

    // 优化 将空间复杂度优化为O(1) 力扣官方题解
    public static int[] productExceptSelf2(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length, R = 1;
        int[] res = new int[n];
        // 这里我们用res也就是结果数组来计算左缀积
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res[i] = nums[i];
            } else {
                res[i] = res[i - 1] * nums[i];
            }
        }
        //这里我们用R这个变量来计算右边的积
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1) {
                res[i] = res[i - 1];
                R = nums[i];
            } else if (i == 0) {
                res[i] = R;
            } else {
                res[i] = R * res[i - 1];
                R *= nums[i];
            }
        }
        return res;
    }
}
